#include <bits/stdc++.h>
using namespace std;
#define ls (u << 1)
#define rs (u << 1 | 1)
const int N = 500010;
int n, m, w[N];
struct node {
  int l, r, sum,  // 区间之和
      lmax,       // [l, ...] 中最大值
      rmax,       // [..., r] 中最大值
      tmax;       // 区间中最大连续子段长度
} tr[N * 4];
void pushup(node &u, const node &l, const node &r) {
  u.sum = l.sum + r.sum;
  u.lmax = max(l.lmax, l.sum + r.lmax);
  u.rmax = max(l.rmax + r.sum, r.rmax);
  u.tmax = max({l.rmax + r.lmax, l.tmax, r.tmax});
}
void pushup(int u) { pushup(tr[u], tr[ls], tr[rs]); }
void build(int u, int l, int r) {
  if (l == r)
    tr[u] = {l, r, w[r], w[r], w[r], w[r]};
  else {
    tr[u] = {l, r, 0, 0, 0, 0};
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(u);
  }
}
void modify(int u, int idx, int val) {
  if (tr[u].l == tr[u].r)
    tr[u] = {idx, idx, val, val, val, val};
  else {
    int mid = tr[u].l + tr[u].r >> 1;
    if (idx <= mid)
      modify(ls, idx, val);
    else if (idx >= mid + 1)
      modify(rs, idx, val);
    else
      assert(false);
    pushup(u);
  }
}
node query(int u, int l, int r) {
  if (l <= tr[u].l && tr[u].r <= r)
    return tr[u];
  else {
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid)
      return query(ls, l, r);
    else if (l >= mid + 1)
      return query(rs, l, r);
    else {
      node res;
      pushup(res, query(ls, l, r), query(rs, l, r));
      return res;
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> w[i];
  build(1, 1, n);
  while (m--) {
    int op;
    cin >> op;
    if (op == 1) {
      int l, r;
      cin >> l >> r;
      if (l > r) swap(l, r);
      cout << query(1, l, r).tmax << endl;
    } else if (op == 2) {
      int idx, val;
      cin >> idx >> val;
      modify(1, idx, val);
    } else
      assert(false);
  }
}
